/**************************************************************************
* File:            topsort.h	                                          *
* Description:     Topological sort of oriented graph                     *
* Author:          Zhuk Artsem, 399                                       *
**************************************************************************/
#pragma once

#include "graph.h"
#include "search.h"
#include <algorithm>
#include <vector>

class TopologicalSortVisitor :public Visitor{
private:
	std::vector<int> list_;
	std::vector<bool> currentlyVisiting_;
	bool hasCycle_;
public:
	TopologicalSortVisitor() : hasCycle_(false){}

	void setGraphSize(int verticesNumber){
		currentlyVisiting_.resize(verticesNumber);
	}

	void enterVertex(int vertex){
		currentlyVisiting_[vertex] = true;
	}

	void enterEdge(int from, int toAdd){
		if (currentlyVisiting_[toAdd] && toAdd!=from)
			hasCycle_ = true;
		/*I think exception here is bad idea.
		* Some times we want to know
		* Is graph acyclyc or not.
		*/
	}


	void leaveVertex(int vertex){
		list_.push_back(vertex);
		currentlyVisiting_[vertex] = false;
	}

	void leaveEdge(int from, int to){}

	std::vector<int> getList(){
		reverse(list_.begin(), list_.end());
		return list_;
	}

	void reset(){
		/*for muliple usage*/
		list_.clear();
		currentlyVisiting_.clear();
		hasCycle_ = false;
	}

	bool hasCycle() const {
		return hasCycle_;
	}
};


std::vector<int> topSort(Graph const * graph){


	TopologicalSortVisitor visitor;

	visitor.setGraphSize(graph->getVerticesNumber());

	runDFS(graph, &visitor);

	std::vector<int> list = visitor.getList();

	if (visitor.hasCycle())
		list.clear();


	return list;
}

